/**
 * @file
 */

#include "canonical_graph.h"

/**
 * 
 */
CanonicalGraph::CanonicalGraph(int vertices): vertices_(vertices)
{
  vertex_labels_ = new int[vertices_];
  adjacency_matrix_ = new int[vertices_  * vertices_];
  adjacency_matrix_copy_ = new int[vertices_  * vertices_];
  adjacency_matrix_min_ = new int[vertices_  * vertices_];

  for(int i = 0; i < vertices_ * vertices_; i++)
      adjacency_matrix_[i] = 0;
}

/**
 * 
 */
CanonicalGraph::~CanonicalGraph()
{
  delete vertex_labels_;
  delete adjacency_matrix_;
  delete adjacency_matrix_copy_;
  delete adjacency_matrix_min_;
}

/**
 * 
 */
bool CanonicalGraph::add_vertex(int id, int label)
{
  if (id < vertices_)
    {
      vertex_labels_[id] = label;
      return true;
    }
  else
    return false; 
}

/**
 * 
 */
bool CanonicalGraph::add_edge(int v1_id, int v2_id, int label)
{
  if ((v1_id < vertices_) && (v2_id < vertices_))
    {
      adjacency_matrix_[v1_id * vertices_ + v2_id] = label;
      adjacency_matrix_[v2_id * vertices_ + v1_id] = label;
    }
  else
    return false;
}

/**
 * 
 */
bool CanonicalGraph::swap_vertices(int loc1, int loc2)
{
  if ((loc1 < vertices_) && (loc1 < vertices_))
    {
      int temp = vertex_labels_[loc1];
      vertex_labels_[loc1] = vertex_labels_[loc2];
      vertex_labels_[loc2] = temp;
    }
  else
    return false;
}

/**
 * 
 */
bool CanonicalGraph::swap_edges(int loc1, int loc2)
{
  if ((loc1 < vertices_) && (loc1 < vertices_))
    {
      for(int i = 0; i < vertices_; i++)
        {
          int temp = adjacency_matrix_[i * vertices_ + loc1]; 
          adjacency_matrix_[i * vertices_ + loc1] = adjacency_matrix_[i * vertices_ + loc2];
          adjacency_matrix_[i * vertices_ + loc2] = temp;
        }

      for(int i = 0; i < vertices_; i++)
        {
          int temp = adjacency_matrix_[vertices_ * loc1 + i]; 
          adjacency_matrix_[vertices_ * loc1 + i] = adjacency_matrix_[vertices_ * loc2 + i];
          adjacency_matrix_[vertices_ * loc2 + i] = temp;
        }
    }
  else
    return false;
}

/**
 * 
 */
void CanonicalGraph::sort_vertices()
{
  for (int i = 0; i < vertices_; i++)
    for (int j = i; j < vertices_; j++)
      if (vertex_labels_[i] > vertex_labels_[j])
        {
          swap_vertices(i,j);
          swap_edges(i,j);
        }
}

/**
 * 
 */
void CanonicalGraph::generate_order_adjacency(std::vector<int> order)
{
  for(int i = 0; i < vertices_; i++)
    for(int j = 0; j < vertices_; j++)
      adjacency_matrix_[order[i] * vertices_ + order[j]] = adjacency_matrix_copy_[i * vertices_ + j]; 
}

/**
 * 
 */
void CanonicalGraph::create_adjacency_copy()
{
  for(int i = 0; i < vertices_ * vertices_; i++)
    adjacency_matrix_copy_[i] = adjacency_matrix_[i];
}

/**
 * 
 */
void CanonicalGraph::init_adjacency_min()
{
  for(int i = 0; i < vertices_ * vertices_; i++)
    adjacency_matrix_min_[i] = adjacency_matrix_[i];
}

/**
 * 
 */
void CanonicalGraph::update_adjacency_min()
{
  bool replace = false;
  for(int i = 0; i < vertices_ * vertices_; i++)
    if ( adjacency_matrix_[i] != adjacency_matrix_min_[i] )
      {
        if (adjacency_matrix_[i] < adjacency_matrix_min_[i])
          replace = true;        
        break;
      }

  if(replace)
    for(int i = 0; i < vertices_ * vertices_; i++)
      adjacency_matrix_min_[i] = adjacency_matrix_[i];
}

/**
 * 
 */
void CanonicalGraph::generate_canonical_label(std::string *result_location)
{

  sort_vertices();
  
  VectorAppender<int> *vector_appender = new VectorAppender<int>;
  bool previous = false;
  PermuationGenerator<int> *permutation_generator = new PermuationGenerator<int>;
  int previous_value;

  for(int i = 0; i < vertices_; i++)
    {
      if (! previous)
        {
          previous = true;
          previous_value = vertex_labels_[i];
          permutation_generator = new PermuationGenerator<int>;
          permutation_generator->add_element(i);
        }
      else
        {
          if (previous_value == vertex_labels_[i])
            permutation_generator->add_element(i);
          else
            {
              std::set<std::vector<int> > result;
              permutation_generator->generate_permutations();
              permutation_generator->get_permutations(&result);
              delete permutation_generator;

              vector_appender->add_set(result);

              previous_value = vertex_labels_[i];
              permutation_generator = new PermuationGenerator<int>;
              permutation_generator->add_element(i);

            }
        }  
    }

  std::set<std::vector<int> > last_result;
  permutation_generator->generate_permutations();
  permutation_generator->get_permutations(&last_result);

  delete permutation_generator;
  vector_appender->add_set(last_result);
  
  std::set<std::vector< int > > result;
  vector_appender->generate_appends();
  vector_appender->get_appends(&result);
  delete vector_appender;

  init_adjacency_min();
  create_adjacency_copy();
  
  for(std::set<std::vector< int > >::iterator i = result.begin();
      i != result.end();
      i++)
  {
    generate_order_adjacency(*i);
    update_adjacency_min();      
  }

  std::string canonical_label = "";
  for(int i = 0; i < vertices_ ; i++)
    {
      std::ostringstream oss;
      oss << vertex_labels_[i];      
      canonical_label.append(oss.str());
    }

  for(int i = 0; i < vertices_ * vertices_; i++)
    {
      std::ostringstream oss;
      oss << adjacency_matrix_min_[i];
      canonical_label.append("--");      
      canonical_label.append(oss.str());
    }

  *result_location = canonical_label;
}
